package com.rui.study.algorithm.P_零杠一背包_动态规划;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2018-12-28 17:43
 **/
public class Solution1 {

    private int[] items;        // 物品重量

    private int w;              // 背包承重

    private boolean[][] state;  // 记录状态

    public Solution1(int[] items, int w) {
        this.items = items;
        this.w = w;
        this.state = new boolean[items.length][w + 1];
    }

    public int knapsack() {
        state[0][0] = true;
        state[0][items[0]] = true;
        for (int i = 1; i < items.length; i++) {
            for (int j = 0; j <= w; j++) {          // 不放入第i个物品
                state[i][j] = state[i - 1][j];
            }
            for (int j = 0; j <= w - items[i]; j++) {          // 放入第i个物品
                if (state[i-1][j]) {
                    state[i][j + items[i]] = true;
                }
            }
        }

        for (int i = w; i >= 0; i--) {
            if (state[items.length - 1][i]) return i;
        }
        return 0;
    }


    public static void main(String[] args) {
        Solution1 solution = new Solution1(new int[]{3, 4, 5, 7, 8}, 9);
        System.out.println("成功求解- [" + solution.knapsack() + "]");
    }

}
